from string import digits
from LeetCoder import *


class Solution:

    def count(self, num1: str, num2: str, min_sum: int, max_sum: int) -> int:
        ls = sorted([num1, num2])
        L, R = ls[0], ls[1]
        m, n = len(L), len(R)

        @cache
        def f(i: int, limit1: bool, isNum: bool, tot: int, limit2: bool,
              low: bool) -> int:
            if i == n:
                return 1 if min_sum <= tot <= max_sum and (not limit1
                                                           or low) else 0
            ans = 0
            if not isNum:
                ans = f(i + 1, limit1, isNum, tot, False, low)
            floor = 0 if isNum else 1
            ceil = int(R[i]) if limit2 else 9
            for d in range(floor, ceil + 1):
                ans += f(i + 1, limit1 and i < m and d <= int(L[i]), True,
                         tot + d, limit2 and d == ceil, low and i < m
                         and d == int(L[i]))
            return ans

        return f(0, True, False, 0, True, True) % 1000000007


s = Solution()
print(s.count(num1="1", num2="12", min_sum=1, max_sum=8))
print(s.count(num1="1", num2="5", min_sum=1, max_sum=5))
print(s.count("6312", "9416", 29, 30))
print(s.count("1000000007", "2000000014", 1, 400))
